
/*
 * Question: For a given binary tree, an additional head
 * node is added, and the root is its right child. A node's
 * left child is labeled by '0' and right child is labeled
 * by '1'. From the head node to some specified node, the
 * path consists of labels can be regarded as a binary
 * number. Try to propose an algorithm to calculate the
 * decimal number corresponding to the binary number.
 *
 * Date: 01/26/2012
 */

#include <iostream>
#include <cassert>
#include "iofile.h"
#include "sqlist.h"
using namespace std;

class sqlist : public _sqlist<char>{};

int bt2num(sqlist sl, char key)
{
    int i;
    int base;
    int num;

    base = 1;
    num = 0;
    for (i = 1; i <= sl.len; i++)
        if (sl.elem[i] == key)
            break;
    assert(i<=sl.len);
    while (i != 1){
        assert(sl.elem[i] != '#');
        num += (i%2==1?1:0)*base;
        base *= 2;
        i /= 2;
    }
    num += base;
    return num;
}

int main()
{
    sqlist sl;

    open_input("chap06/ex35.txt");
    sqlist_create<sqlist, char>(sl);
    cout << bt2num(sl, 'A') << endl;
    sqlist_destory(sl);
    close_input();
    return 0;
}
